#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30
#define INIFITY 9999
#define M INIFITY
void dfsfunction(int a[MAXSIZE][MAXSIZE], int data[], int n, int v);
int visit[MAXSIZE] = {0};
void dfs(int a[MAXSIZE][MAXSIZE], int data[], int n)
{
    for (int i = 0; i < n; i++)
    {
        if (!visit[i])
        {
            dfsfunction(a, data, n, i);
        }
    }
}
void dfsfunction(int a[MAXSIZE][MAXSIZE], int data[], int n, int v)
{
    visit[v] = 1;
    printf("%3d", data[v]);
    for (int i = 0; i < n; i++)
    {
        if (a[v][i] != 0 && a[v][i] != INIFITY)
        {
            if (!visit[i])
            {
                dfsfunction(a, data, n, i);
            }
        }
    }
}
void stack_dfs(int a[MAXSIZE][MAXSIZE], int data[], int n, int v)
{
    int stack[MAXSIZE];
    int top = -1;
    for (int i = 0; i < n; i++)
    {
        visit[i] = 0;
    }
    stack[++top] = v;

    while (top >= 0)
    {
        int p = stack[top];
        if (!visit[p])
        {
            printf("%3d", data[p]);
            visit[p] = 1;
        }
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[p][i] != 0 && a[p][i] != INIFITY)
            {
                if (!visit[i])
                {
                    stack[++top] = i;
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0)
            top--;
    }
}

void bfs(int a[MAXSIZE][MAXSIZE], int data[], int n, int v)
{
    int queue[MAXSIZE];
    int front, rear;
    front = rear = 0;

    for (int i = 0; i < n; i++)
    {
        visit[i] = 0;
    }
    queue[rear++] = v;
    visit[v] = 1;
    while (front != rear)
    {
        int p = queue[front++];
        printf("%3d", data[p]);
        for (int i = 0; i < n; i++)
        {
            if (a[p][i] != 0 && a[p][i] != INIFITY)
            {
                if (!visit[i])
                {
                    visit[i] = 1;
                    queue[rear++] = i;
                }
            }
        }
    }
}
int main()
{
    /*******************code*******************/
    int data2[8] = {0, 1, 2, 3, 4, 5, 6, 7};

    int a[MAXSIZE][MAXSIZE] = {
        //  0     1   2    3    4    5    6     7
        {0, 1, 1, M, M, M, M, M},
        {1, 0, 1, M, 1, M, M, 1}, //1
        {1, 1, 0, 1, M, M, M, M}, //2
        {M, M, 1, 0, M, 1, M, M}, //3
        {M, 1, 1, M, M, 0, 1, M}, //4
        {M, M, M, 1, 1, 0, 1, M}, //5
        {M, M, M, M, M, 1, 0, 1}, //6
        {M, 1, M, M, M, M, 1, 0}  //7
    };
    printf("DFS:");
    dfs(a, data2, 8);
    printf("\nBFS:");
    bfs(a, data2, 8, 0);
    printf("\nSTACK_DFS:");
    stack_dfs(a, data2, 8, 0);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
